#pragma once

#include <iostream>
#include <vector>
#include <unordered_map>
#include <climits>

using namespace std;

namespace matrix
{
    template <class V, class W, W MAX_W = INT_MAX, bool Direction = false>
    class Graph
    {
    public:
        Graph(const V *v, int n)
        {
            _vertexs.resize(n);
            for (int i = 0; i < n; i++)
            {
                _vertexs[i] = v[i];
                _index_map[v[i]] = i;
            }

            _matrix.resize(n, vector<W>(n, MAX_W));
        }

        size_t GetVertexIndex(const V &v)
        {
            if (_index_map.count(v))
                return _index_map[v];
            else
            {
                throw invalid_argument("vertex error!\n");
                return -1;
            }
        }

        void AddEdge(const V &src, const V &dst, const W &w)
        {
            size_t srci = GetVertexIndex(src), dsti = GetVertexIndex(dst);
            if (srci == dsti)
                return;

            _matrix[srci][dsti] = w;
            if (!Direction)
                _matrix[dsti][srci] = w;
        }

        void Print()
        {
            int n = _vertexs.size();
            for (int i = 0; i < n; i++)
            {
                cout << "[" << i << "]->" << _vertexs[i] << endl;
            }
            cout << endl;

            cout << "  ";
            for (int i = 0; i < n; i++)
            {
                cout << i << ' ';
            }
            cout << endl;

            for (int i = 0; i < n; i++)
            {
                cout << i << ' ';
                for (int j = 0; j < n; j++)
                {
                    cout << (_matrix[i][j] == MAX_W ? 0 : _matrix[i][j]) << ' ';
                }
                cout << endl;
            }
        }

    private:
        vector<V> _vertexs;
        unordered_map<V, size_t> _index_map;
        vector<vector<W>> _matrix;
    };

    void TestGraph()
    {
        Graph<char, int, INT_MAX, true> g("0123", 4);
        g.AddEdge('0', '1', 1);
        g.AddEdge('0', '3', 4);
        g.AddEdge('1', '3', 2);
        g.AddEdge('1', '2', 9);
        g.AddEdge('2', '3', 8);
        g.AddEdge('2', '1', 5);
        g.AddEdge('2', '0', 3);
        g.AddEdge('3', '2', 6);
        g.Print();
    }
}
